package com.asia.algorithmcode.binaryTree;


/**
 * @DESCRIPTION: 110、平衡二叉树
 * @USER: wanfu
 * @DATE: 2025/5/12 星期一 14:19
 */
public class IsBalanced {


    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2_1 = new TreeNode(2);
        TreeNode n2_2 = new TreeNode(2);
        TreeNode n3_1 = new TreeNode(3);
        TreeNode n3_2 = new TreeNode(3);
        TreeNode n4_1 = new TreeNode(4);
        TreeNode n4_2 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);

        n2_1.left = n1;
        n2_1.right = n4_1;
        n4_1.left = n3_1;
        n4_1.right = n5;

        TreeNode t3 = new TreeNode(3);
        TreeNode t9 = new TreeNode(9);
        TreeNode t20 = new TreeNode(20);
        TreeNode t15 = new TreeNode(15);
        TreeNode t7 = new TreeNode(7);

        t3.left = t9;
        t3.right = t20;
        t20.left = t15;
        t20.right = t7;


        System.out.println(new IsBalanced().isBalanced(t3));
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int i = maxDepth(root.left);
        int j = maxDepth(root.right);
        return Math.abs(i - j) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    // 未实现成功的方法
    public int[] dfs(TreeNode root, int ld, int rd) {
        int[] resList = {1, ld, rd};

        if (root.left != null) {
            int[] lefts = dfs(root.left, ld + 1, rd);
            if (lefts[0] == 0 || Math.abs(resList[2] - lefts[1]) > 1) {
                resList[0] = 0;
            }
            resList[1] = Math.max(resList[1], lefts[1]);
        }

        if (root.right != null) {
            int[] rights = dfs(root.right, ld, rd + 1);
            if (rights[0] == 0 || Math.abs(rights[2] - resList[1]) > 1) {
                resList[0] = 0;
            }
            resList[2] = Math.max(resList[2], rights[2]);
        }
        return resList;
    }
}
